package com.xdja.zuoye;

public class Jishengjun {

    public static void main(String[] args) {
        int[] array = new int[]{4, 2, 10, 9, 8, 1, 6};
        sort(array, 0, array.length - 1);
        for (int i : array) {
            System.out.println(i);
        }
        System.out.println("第三小的数字为:" + array[2]);
    }

    private static void sort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int value = array[start];
//        1 2 3
        int i = start;
        int j = end;
        while (i < j) {
            //先看右边，依次往左递减
            while (value <= array[j] && i < j) {
                j--;
            }
            //再看左边，依次往右递增
            while (value >= array[i] && i < j) {
                i++;
            }

            if (i < j) {
                array[i] = array[i] ^ array[j];
                array[j] = array[i] ^ array[j];
                array[i] = array[i] ^ array[j];
            }
        }
        //最后将基准为与i和j相等位置的数字交换
        array[start] = array[i];
        array[i] = value;

        sort(array, start, j - 1);
        sort(array, j + 1, end);
    }
}
